The present invention relates to an optimized division circuit and method for implementing the optimized division circuit.
Digital division as implemented in a computer consists of a series of preliminary operations, e.g., normalization of the values for the dividend and divisor into binary normalized positive fractional form and an iterative division process, and a terminal operation, e.g., changing the form of the remainder. The iterative division process is defined by the following equation: EQU P.sub.j+1 =rp.sub.j -q.sub.j+1 d, (1)
where:
j=the iterative index=0, 1, . . . , m-1; PA1 p.sub.j =the partial remainder used in the jth cycle; PA1 rp.sub.j =the jth radix-modified remainder; PA1 r=the radix; PA1 p.sub.0 =the dividend; PA1 p.sub.m =the remainder; PA1 q.sub.j =the jth quotient digit in which the quotient is of the form q.sub.0, q.sub.1, q.sub.2, . . . , q.sub.m where m=the number of digits (using radix r) in the quotient; PA1 d=the divisor; and PA1 q.sub.j+1 d=the jth divisor multiple.
The basic approach is to begin with an initial guess for a quotient which is known to be within some boundaries, and then to improve upon this guess at each iteration. A nonrestoring algorithm technique can be used to select a quotient value. This algorithm allows an inexact quotient value to be selected and later corrected in the next iteration.
There are four distinct operations required per division iteration. The process consists of forming the correct divisor multiple (q.sub.j+1 d), forming the proper radix modified remainder (rp.sub.j), subtracting the divisor multiple from the modified remainder and choosing the next quotient digit.
Assuming a radix equal to 4, the modified remainder can be formed by a two bit left shift of the present partial remainder. This operation is required to align the values for proper subtraction. Shifting the present partial remainder to the left is preferred over shifting the divisor multiple to the right to save hardware. Shifting the present partial remainder allows the dividend register to remain only as wide as the original dividend and not be extended to the length of the original dividend plus the width of the final quotient as right shifting the divisor multiple would. This left-shift alignment is very fast because it is done for every two bits. In radix 4 division every two quotient bits equals one radix 4 quotient digit, and one radix 4 quotient digit is determined per iteration.
The divisor multiple formation consists of multiplying the divisor by the selected quotient digit. The speed of this step depends on the range of the quotient values which may be chosen for the selected quotient digit term. Quotient digits have the values 0, 1, 2, . . . , r-1. A radix 4 nonrestoring division therefore requires that multiples of 1, 2, and 3 times the divisor be available for subtraction from the present partial remainder. Divisor multiple values representing x1, x2, x0 multiplications, may be formed easily by shifting (x2), latching (x1) or clearing (x0). Divisor multiples representing x3 multiplications, however, take more time and require extra hardware because they require a tripler circuit or the addition of 1x and 2x the divisor values, and the term must then be stored in an auxiliary register. To minimize the time for the critical path through the division process, it is important to limit the range of available quotient digits to quotient digits which may be formed by simple shifts and the complements of those digits. For radix 4 these digits would be -2,-1, 0, 1 and 2.
The need to restrict the range of possible quotient digits can be applied as follows: at least r unique digits are required to represent a number in radix r. In the representation introduced above, there are 2n+1 unique digits, where n represents the highest quotient digit value. Thus, 2n+1.gtoreq.r. On the other hand, for a radix r, the maximum value for a quotient digit n should not be greater than the value of the maximum digit representable, thus n.ltoreq.r-1.
Using positive and negative values for the quotient digits introduces redundancy into the representation of the quotient.
If 2n (where n is the highest quotient digit value or, in the example, 2) is greater than r-1 (r is the radix), then there are more symbols available to represent a number than is actually necessary. Therefore, some numerical values may be represented in more than one form. For example, for a radix of 4, the number 6 could be represented as 12 (i.e., 4+2) or 2(-2) (i.e., 8-2). This redundancy permits less precision in comparing the divisor and partial remainder in selecting a quotient digit, thereby enhancing the speed of the division process.
With the quotient representation now defined, the range restrictions on the partial remainders may be derived. When determining whether a quotient digit is correct or not, one is essentially applying the restriction for positive partial remainders that 0.ltoreq.p.sub.j+1 &lt;d, where p.sub.j+1 is the difference between the j+1 th divisor multiple (q.sub.j+1 times the divisor) and the jth partial remainder. If p.sub.j+1 is not within this range, then q.sub.j+1 is changed until it is. For a nonrestoring division, negative partial remainders and negative quotient digits are allowable, and thus the range restriction is EQU .vertline.p.sub.j+1 .vertline..ltoreq..vertline.d.vertline.(2)
One prior method to implement the iterative division relationship defined in Equation (1) was described by George S. Taylor in "Compatible Hardware For Division and Square Root," Fifth IEEE Symposium on Computer Arithmetic (May, 1981). Taylor proposed the use of a graphical representation of the division procedure to select the next quotient digit in order to form the divisor multiple. The basis for the plot is the iterative relationship defined by equation (1), together with the range restriction calculated above in equation (2) which yields: EQU .vertline.p.sub.j+1 .vertline..ltoreq.(n/r-1)d. (3)
FIG. 1 illustrates the plot defined by Taylor which is essentially a plot of partial remainder (P) versus divisor (D) values and has been referred to as a "P-D plot."
Solving the recursive relationship in equation (1) for rp.sub.j yields: EQU rp.sub.j =p.sub.j+1 +q.sub.j+1 d, (4)
For a fixed quotient digit, the upper limit of rp.sub.j as a function of the divisor d occurs when p.sub.j+1 is maximum, i.e., when: EQU p.sub.j+1 =(n/r-1)d,
and thus EQU rp.sub.jmax =((n/r-1)+q.sub.j+1)d, (5)
Likewise the lower limit occurs when: EQU p.sub.j+1 =(-n/r-1)d,
and thus: EQU rp.sub.jmin =((-n/r-1)+q.sub.j+1)d, (6)
These linear equations may be plotted as functions of d with q.sub.j+1 as a parameter ranging from -n to +n in steps of 1. The area between rp.sub.jmax and rp.sub.jmin for a given q.sub.j+1 =i will be denoted as the "q(i) area."
The division procedure was then defined such that a given value of divisor d and the jth shifted partial remainder will specify a point in a q(i) area. The digit i was defined as the value of the next quotient digit q.sub.j+1 which in turn is used in forming the next partial remainder. In this representation, the redundancy in the quotient digit selection is manifested as overlapping of the q(i) regions, i.e., some pairs of d and rp.sub.j will specify a point for which either q.sub.j+1 =i or q.sub.j+1 =i-1 is a valid choice.
FIG. 1 is an example of a P-D plot for a division with r=4 and n=2. The region for which q.sub.j+1 =2 is a valid choice, i.e., the q(2) area, lies between lines 2' and 2; the q(1) area lies between lines 1' and 1, and so forth. Note that in the overlap between q(i) areas, for example, the region between lines 1' and 2, either choice q.sub.j+1 =1 or q.sub.j+1 =2 is correct. Note further that the figure is symmetric about both axes.
On the right half of FIG. 1, "steps" have been drawn within the overlap of the q(i) regions. The width of a "step" (constant rp.sub.j, d varying) defines a "divisor interval," the value of rp.sub.j for each step defines a comparison constant, and the distance between comparison constants defines a "partial remainder interval." Phrased in this terminology, division consists of locating a given divisor value within the appropriate divisor interval (using comparison constants), and selecting a value of q.sub.j+1 enclosed by the intersection of the boundaries of these intervals. Since a divisor and partial remainder must be located only to within an "interval," they need not be inspected to full precision in selecting a correct quotient digit.
The length of a divisor interval is limited by the boundaries of the overlap region. The maximum precision of inspection is required where the divisor interval is minimum. To determine where this minimum interval occurs, consider for a given value of rp.sub.j, the maximum width of a divisor interval is: ##EQU1## where R=(r-1).
The interval .DELTA.d is minimum when i is maximum and rp.sub.j is minimum. The maximum value of i is n; the minimum of rp.sub.j for q.sub.j+1 =n will occur when the upper bound of the overlap region intersects d=1/2, i.e., when d.sub.1 =1/2. The precision of required inspection is thus determined by the divisor interval closest to d=1/2 and between q.sub.j+1 =n and q.sub.j+1 =n-1.
Taylor's technique uses the P-D plot to decode the divisor interval and partial remainder interval, and to select the quotient digit indicated by their intersection. He also proposed generating a look-up table based on the plot. This look-up table was then used to form logical equations to define and implement a division circuit.
This method has several disadvantages, however. First, the P-D plot must be constructed manually and there is a certain amount of imprecision in the defined boundaries of the plot which therefore introduces some imprecision into the selection of a quotient. Second, Taylor's table is incomplete because the method is not precise in its inspections of combinations of divisors and partial remainders. The circuit for performing the division operation is thus implemented by inspection of the incomplete look-up table and has proven to be difficult to construct requiring a large number of stages of logical gates thus reducing the speed of the division operation.